{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Verifying an Alien Dictionary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isAlienSorted"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #验证外星语词典"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>某种外星语也使用英文小写字母，但可能顺序 <code>order</code> 不同。字母表的顺序（<code>order</code>）是一些小写字母的排列。</p>\n",
    "\n",
    "<p>给定一组用外星语书写的单词 <code>words</code>，以及其字母表的顺序 <code>order</code>，只有当给定的单词在这种外星语中按字典序排列时，返回 <code>true</code>；否则，返回 <code>false</code>。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"hello\",\"leetcode\"], order = \"hlabcdefgijkmnopqrstuvwxyz\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>在该语言的字母表中，'h' 位于 'l' 之前，所以单词序列是按字典序排列的。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"word\",\"world\",\"row\"], order = \"worldabcefghijkmnpqstuvxyz\"\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>在该语言的字母表中，'d' 位于 'l' 之后，那么 words[0] > words[1]，因此单词序列不是按字典序排列的。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"apple\",\"app\"], order = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>当前三个字符 \"app\" 匹配时，第二个字符串相对短一些，然后根据词典编纂规则 \"apple\" > \"app\"，因为 'l' > '∅'，其中 '∅' 是空白字符，定义为比任何其他字符都小（<a href=\"https://baike.baidu.com/item/%E5%AD%97%E5%85%B8%E5%BA%8F\" target=\"_blank\">更多信息</a>）。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= words.length <= 100</code></li>\n",
    "\t<li><code>1 <= words[i].length <= 20</code></li>\n",
    "\t<li><code>order.length == 26</code></li>\n",
    "\t<li>在 <code>words[i]</code> 和 <code>order</code> 中的所有字符都是英文小写字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [verifying-an-alien-dictionary](https://leetcode.cn/problems/verifying-an-alien-dictionary/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [verifying-an-alien-dictionary](https://leetcode.cn/problems/verifying-an-alien-dictionary/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"hello\",\"leetcode\"]\\n\"hlabcdefgijkmnopqrstuvwxyz\"', '[\"word\",\"world\",\"row\"]\\n\"worldabcefghijkmnpqstuvxyz\"', '[\"apple\",\"app\"]\\n\"abcdefghijklmnopqrstuvwxyz\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        index = {c:i for i,c in enumerate(order)}\n",
    "        return all(s <= t for s,t in pairwise([index[c] for c in word] for word in words))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        index = {c: i for i, c in enumerate(order)}\n",
    "        return all(s <= t for s, t in pairwise([index[c] for c in word] for word in words))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        char_index_map = {}\n",
    "        for i, v in enumerate(order):\n",
    "            char_index_map[v] = i\n",
    "\n",
    "        def compare_word(w1, w2):\n",
    "            min_len = min(len(w1), len(w2))\n",
    "            for j in range(min_len):\n",
    "                if char_index_map[w1[j]] > char_index_map[w2[j]]:\n",
    "                    return False\n",
    "                elif char_index_map[w1[j]] == char_index_map[w2[j]]:\n",
    "                    continue\n",
    "                else:\n",
    "                    return True\n",
    "            if len(w1) > len(w2):\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        \n",
    "        if len(words) <= 1:\n",
    "            return True\n",
    "        \n",
    "        for i in range(len(words) - 1):\n",
    "            if compare_word(words[i], words[i+1]):\n",
    "                continue\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        def check(a, b):\n",
    "            m, n = len(a), len(b)\n",
    "            i, j = 0, 0\n",
    "            while i < m and j < n:\n",
    "                if a[i] != b[j]:\n",
    "                    return ord[a[i]] - ord[b[j]]\n",
    "\n",
    "                i += 1\n",
    "                j += 1\n",
    "            if i < m:\n",
    "                return 1\n",
    "            if j < n:\n",
    "                return -1\n",
    "\n",
    "            return 0\n",
    "\n",
    "            pass\n",
    "\n",
    "        ord = {}\n",
    "        for i, c in enumerate(order):\n",
    "            ord[c] = i\n",
    "\n",
    "        n = len(words)\n",
    "        for i in range(1, n):\n",
    "            if check(words[i - 1], words[i]) > 0:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "#         def check(a, b):\n",
    "#             m, n = len(a), len(b)\n",
    "#             i, j = 0, 0\n",
    "#             while i < m and j < n:\n",
    "#                 if a[i] != b[j]:\n",
    "#                     return ord[a[i]] - ord[b[j]]\n",
    "#                 i += 1\n",
    "#                 j += 1\n",
    "\n",
    "#             if i < m:\n",
    "#                 return 1\n",
    "#             if j < n:\n",
    "#                 return -1\n",
    "#             return 0\n",
    "\n",
    "#         ord = {}\n",
    "#         for i, c in enumerate(order):\n",
    "#             ord[c] = i\n",
    "\n",
    "#         n = len(words)\n",
    "#         for i in range(1, n):\n",
    "#             if check(words[i - 1], words[i]) > 0:\n",
    "#                 return False\n",
    "#         return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "         return words == sorted(words, key=lambda x: list(map(order.index, x)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        m=len(words)\n",
    "        i,j=0,0\n",
    "        if len(words)==1:\n",
    "            return True\n",
    "        while i<m-1:\n",
    "            j=0\n",
    "            while(j<len(words[i]) and j<len(words[i+1])):\n",
    "                l1,l2=order.find(words[i][j]),order.find(words[i+1][j])\n",
    "                if(l1<l2):\n",
    "                    break\n",
    "                elif(l1==l2):\n",
    "                    j=j+1\n",
    "                else:\n",
    "                    return False\n",
    "            if(j==len(words[i+1]) and j<len(words[i])):\n",
    "                return False\n",
    "            i=i+1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        dct = {va: i for i, va in enumerate(order)}\n",
    "        pre = [dct[w] for w in words[0]]\n",
    "        for word in words[1:]:\n",
    "            cur = [dct[w] for w in word]\n",
    "            if pre > cur:\n",
    "                return False\n",
    "            pre = cur\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        hash_map={c:i for i,c in enumerate(order)}\n",
    "        for i in range(1,len(words)):\n",
    "            for c1,c2 in zip(words[i-1],words[i]):\n",
    "                if c1!=c2:\n",
    "                    if hash_map[c1]>hash_map[c2]:\n",
    "                        return False\n",
    "                    else:\n",
    "                        break\n",
    "            else:\n",
    "                if len(words[i-1])>len(words[i]):\n",
    "                    return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: list[str], order: str) -> bool:\n",
    "        d = {val: idx for idx, val in enumerate(order)}\n",
    "        for i in range(len(words)-1):\n",
    "            word1 = words[i]\n",
    "            word2 = words[i+1]\n",
    "            for j, (char1, char2) in enumerate(zip(word1, word2)):\n",
    "                if d[char1] > d[char2]:\n",
    "                    return False\n",
    "                if d[char1] < d[char2]:\n",
    "                    break\n",
    "            if len(word1) > len(word2) and word1.startswith(word2):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        # word1 > word2，返回True。包括重叠字符相同，且word1长度 > word2长度\n",
    "        def bigger(word1: str, word2: str) -> bool:\n",
    "            n1, n2 = len(word1), len(word2)\n",
    "            for j in range(min(n1, n2)):\n",
    "                if d[word1[j]] > d[word2[j]]:\n",
    "                    return True\n",
    "                elif d[word1[j]] < d[word2[j]]:\n",
    "                    return False\n",
    "            return n1 > n2\n",
    "\n",
    "        #\n",
    "        if len(words) <= 1:\n",
    "            return True\n",
    "        # 计算每个字符的字典序（索引）\n",
    "        d = defaultdict(int)\n",
    "        for i, c in enumerate(order):\n",
    "            d[c] = i\n",
    "        #\n",
    "        for i in range(len(words) - 1):\n",
    "            if bigger(words[i], words[i + 1]):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        if len(words) <= 1:\n",
    "            return True\n",
    "        d = { i: idx for idx, i in enumerate(order)}\n",
    "        def is_order(w1, w2):\n",
    "            m, n = len(w1), len(w2)\n",
    "            for i in range(min(m,n)):\n",
    "                if d[w1[i]] > d[w2[i]]:\n",
    "                    return False\n",
    "                elif d[w1[i]] < d[w2[i]]:\n",
    "                    return True\n",
    "            return m <= n\n",
    "        for i in range(len(words)-1):\n",
    "            if not is_order(words[i], words[i+1]):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        index_map = {c: i for i, c in enumerate(order)}\n",
    "\n",
    "        def word_to_index(word):\n",
    "            return [index_map[c] for c in word]\n",
    "\n",
    "        for i in range(len(words) - 1):\n",
    "            word1 = word_to_index(words[i])\n",
    "            word2 = word_to_index(words[i + 1])\n",
    "\n",
    "            if word1 > word2:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: list[str], order: str) -> bool:\n",
    "        d = {val: idx for idx, val in enumerate(order)}\n",
    "        for i in range(len(words)-1):\n",
    "            word1 = words[i]\n",
    "            word2 = words[i+1]\n",
    "            len1 = len(word1)\n",
    "            len2 = len(word2)\n",
    "            for j in range(min(len1, len2)):\n",
    "                if d[word1[j]] > d[word2[j]]:\n",
    "                    return False\n",
    "                if d[word1[j]] == d[word2[j]]:\n",
    "                    continue\n",
    "                break\n",
    "            j += 1\n",
    "            if (j == len2) and (j != len1) and (word1[j-1]==word2[j-1]):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        p = {o : i for i, o in enumerate(order)}\n",
    "        return words == sorted(words, key= lambda word : [p[c] for c in word])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        if len(words) == 1:\n",
    "            return True\n",
    "\n",
    "        orderDic = dict()\n",
    "        for i in range(len(order)):\n",
    "            orderDic[order[i]] = i+1\n",
    "        orderDic['.'] = 0\n",
    "\n",
    "        for i in range(len(words)-1):\n",
    "            # 前面的长度不大于后面的\n",
    "            pre,nxt = words[i], words[i+1]\n",
    "            # 补足长度\n",
    "            if len(nxt) > len(pre):\n",
    "                for j in range(len(nxt)-len(pre)):\n",
    "                    pre += '.'\n",
    "            if len(pre) > len(nxt):\n",
    "                for j in range(len(pre)-len(nxt)):\n",
    "                    nxt += '.'\n",
    "            #从前到后依次比较\n",
    "            for k in range(len(pre)):\n",
    "                if orderDic[pre[k]] < orderDic[nxt[k]]:\n",
    "                    break\n",
    "                if orderDic[pre[k]] > orderDic[nxt[k]]:\n",
    "                    return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        n = len(words)\n",
    "        for i in range(n-1):\n",
    "            n1 = len(words[i])\n",
    "            n2 = len(words[i+1])\n",
    "            k = n2 if n1>n2 else n1\n",
    "            for j in range(k):\n",
    "                if words[i][j] == words[i+1][j]:\n",
    "                    continue\n",
    "                else:\n",
    "                    inx1 = order.find(words[i][j])\n",
    "                    indx2 = order.find(words[i+1][j])\n",
    "                    if inx1 > indx2:\n",
    "                        return False\n",
    "                    break\n",
    "            else:        \n",
    "                if n1 > n2:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        \n",
    "        #一一对应到数字\n",
    "        chcount = {}\n",
    "        for i in range(len(order)):\n",
    "            chcount[order[i]] = i\n",
    "        # 算一个最长的长度出来\n",
    "        maxlen = 0\n",
    "        for word in words:\n",
    "            maxlen = max(len(word), maxlen)\n",
    "        \n",
    "        for i in range(1, len(words)):\n",
    "            valid = False\n",
    "            # for j in range(len(words[i-1])):\n",
    "            j = 0\n",
    "            while j < len(words[i - 1]) and j < len(words[i]):\n",
    "                prev = chcount[words[i - 1][j]]\n",
    "                curr = chcount[words[i][j]]\n",
    "                print(words[i-1],words[i],words[i-1][j],words[i][j],i,j)\n",
    "                # 遇到第一个小于的\n",
    "                if prev < curr:\n",
    "                    valid = True\n",
    "                    break\n",
    "                elif prev > curr:\n",
    "                    return False\n",
    "                j += 1\n",
    "            if not valid:\n",
    "                if len(words[i - 1]) > len(words[i]):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        d = str.maketrans({order[i]: chr(ord('a') + i) for i in range(26)})\n",
    "        prev = ''\n",
    "        for w in words:\n",
    "            w = w.translate(d)\n",
    "            if prev > w:\n",
    "                return False\n",
    "            prev = w\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from collections import *\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        ch_map={ch:chr(ord('a')+i) for i, ch in enumerate(order)}\n",
    "        nwords1=[]\n",
    "        nwords2=[]\n",
    "        for word in words:\n",
    "            s=''.join([ch_map[ch] for ch in word])\n",
    "            nwords1.append(s)\n",
    "            nwords2.append(s)\n",
    "        nwords1.sort()\n",
    "        return nwords1==nwords2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        new_dic={}\n",
    "        for i,k in enumerate(order):\n",
    "            new_dic[k]=i\n",
    "        l=len(words)\n",
    "        for i in range(l-1):\n",
    "            L=len(words[i])\n",
    "            for k in range(L):\n",
    "                if k > len(words[i+1])-1:\n",
    "                    return False\n",
    "                a,b=new_dic[words[i][k]],new_dic[words[i+1][k]]\n",
    "                if a < b:\n",
    "                    break\n",
    "                if a > b:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        index_map = {c: i for i, c in enumerate(order)}\n",
    "\n",
    "        def word_to_index(word):\n",
    "            return [index_map[c] for c in word]\n",
    "\n",
    "        for i in range(len(words) - 1):\n",
    "            word1 = word_to_index(words[i])\n",
    "            word2 = word_to_index(words[i + 1])\n",
    "\n",
    "            if word1 > word2:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:        \n",
    "        for i in range(len(words)-1):\n",
    "            pre = [order.index(x) for x in words[i]]\n",
    "            cur = [order.index(x) for x in words[i+1]]\n",
    "            print(pre,cur)\n",
    "            if pre > cur:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        index = {c: i for i, c in enumerate(order)}\n",
    "        return all(s <= t for s, t in pairwise([index[c] for c in word] for word in words))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        cmp = sorted(words,key = lambda x: [order.index(i) for i in x])\n",
    "        return cmp == words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        d = str.maketrans(order, ascii_lowercase)\n",
    "        return all(w1.translate(d) <= w2.translate(d) for w1, w2 in pairwise(words))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        def isSort(s, t):\n",
    "            if s[0] == t[0] and t in s and t != s:\n",
    "                return False\n",
    "            for i in range(min(len(s), len(t))):\n",
    "                if s[i] != t[i]:\n",
    "                    if order.index(s[i]) > order.index(t[i]):\n",
    "                        return False\n",
    "                    else:\n",
    "                        return True\n",
    "            return True\n",
    "\n",
    "        for i in range(len(words) - 1):\n",
    "            if not isSort(words[i], words[i + 1]):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        mp={c:i for i,c in enumerate(order)}\n",
    "        for i,w in enumerate(words[:-1]):\n",
    "            j=0\n",
    "            while j<len(w):\n",
    "                if j==len(words[i+1]) or (a:=mp[w[j]] - mp[words[i+1][j]])>0:\n",
    "                    return False\n",
    "                elif a<0:\n",
    "                    break\n",
    "                j+=1\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        f = False\n",
    "        \n",
    "        for i in range(len(words) - 1):\n",
    "            for j in range(i + 1, len(words)):\n",
    "                s1, s2 = words[i], words[j]\n",
    "\n",
    "                if s1 == s2:\n",
    "                    f = True\n",
    "                    break\n",
    "\n",
    "                k = 0\n",
    "                while k < len(s1):\n",
    "                    if k < len(s2) and order.index(s1[k]) > order.index(s2[k]):\n",
    "                        return False\n",
    "                    elif k < len(s2) and order.index(s1[k]) < order.index(s2[k]):\n",
    "                        f = True\n",
    "                        break    \n",
    "                    k += 1\n",
    "\n",
    "                if k < len(s2):\n",
    "                    f = True\n",
    "                else:\n",
    "                    f = False\n",
    "    \n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        # 自定义排序序列 一行流\n",
    "        return words == sorted(words,key=lambda s:''.join(['abcdefghijklmnopqrstuvwxyz'[order.index(i)] for i in s]))\n",
    "        \n",
    "        # MAP 逐个遍历 代码优化\n",
    "        def checkOrder(valueA, valueB):\n",
    "            for itemA, itemB in zip(valueA, valueB):\n",
    "                if orderDic[itemA] != orderDic[itemB]:\n",
    "                    return orderDic[itemA]<orderDic[itemB]  # 配对字符比序列\n",
    "            return len(valueA)<=len(valueB)  # 全相等比长度\n",
    "        orderDic={value:key for key, value in enumerate(order)}\n",
    "        return all(checkOrder(valueA, valueB) for valueA, valueB in zip(words, words[1:]))\n",
    "\n",
    "        # MAP 逐个遍历\n",
    "        ind = {c: i for i, c in enumerate(order)}\n",
    "        for a, b in zip(words, words[1:]):  # 自配对 1&2 2&3 3&4 ...\n",
    "            if len(a) > len(b) and a[:len(b)] == b:  # case abcde&abc \n",
    "                return False\n",
    "            for s1, s2 in zip(a, b):\n",
    "                if ind[s1] < ind[s2]:\n",
    "                    break\n",
    "                elif ind[s1] > ind[s2]:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "        # MAP C->INT\n",
    "        dic = {}\n",
    "        for i, c in enumerate(order):\n",
    "            dic[c] = str(i + 10)\n",
    "        pre = '0'\n",
    "        for w in words:\n",
    "            cur = ''\n",
    "            for c in w:\n",
    "                cur += dic[c]\n",
    "            mx = max(len(cur), len(pre))\n",
    "            if int(pre + '0' * (mx-len(pre))) > int(cur + '0' * (mx-len(cur))): \n",
    "                return False\n",
    "            pre = cur\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        order = {j:i for i,j in enumerate(order)}\n",
    "        ans = [order[i] for i in words[0]]\n",
    "        for j in words[1:]:\n",
    "            tmp = [order[i] for i in j]\n",
    "            if ans > tmp:\n",
    "                return False\n",
    "            ans = tmp\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        d = {c:i for i, c in enumerate(order)}\n",
    "        a = [d[c] for c in words[0]]\n",
    "        for word in words[1:]:\n",
    "            b = [d[c] for c in word]\n",
    "            if b < a:\n",
    "                return False\n",
    "            a = b\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        d = {char:i for i,char in enumerate(order)}\n",
    "        pre = [d[l] for l in words[0]]\n",
    "        for word in words[1:]:\n",
    "            cur = [d[l] for l in word]\n",
    "            if pre > cur:\n",
    "                return False\n",
    "            pre = cur\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        d = str.maketrans(order, ascii_lowercase)\n",
    "        print(d)\n",
    "        for w1, w2 in pairwise(words):\n",
    "            if w1.translate(d)>w2.translate(d):\n",
    "                return False\n",
    "        return True\n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        # 思路：这道题题意比较难理解，它是要分析2个单词的子母，从头开始比较\n",
    "        # 如果前大后小，直接False，如果前小后大， 则再遍历下2个单词\n",
    "        # 如果2个单词的子母相等，则比较下一个子母\n",
    "        dic = {}\n",
    "        for k, v in enumerate(order):\n",
    "            dic[v] = k\n",
    "        for i in range(len(words) - 1):\n",
    "            tmp1 = words[i]\n",
    "            tmp2 = words[i + 1]\n",
    "            for j in range(max(len(tmp1), len(tmp2))):\n",
    "                # 谁先遍历完，谁就赋小值，比如-1，方便下一轮比较\n",
    "                idx1 = dic[tmp1[j]] if j < len(tmp1) else -1\n",
    "                idx2 = dic[tmp2[j]] if j < len(tmp2) else -1\n",
    "                if idx1 > idx2:\n",
    "                    return False\n",
    "                elif idx1 < idx2:\n",
    "                    break\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import pairwise\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        dic = {val: idx for idx, val in enumerate(order)}\n",
    "        for w1, w2 in pairwise(words):\n",
    "            idx = 0\n",
    "            while idx < len(w1):\n",
    "                if idx == len(w2):\n",
    "                    return False\n",
    "                diff = dic[w1[idx]] - dic[w2[idx]]\n",
    "                if diff > 0:\n",
    "                    return False\n",
    "                elif diff < 0:\n",
    "                    break\n",
    "                idx += 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        # MAP 逐个遍历\n",
    "        def checkOrder(valueA, valueB):\n",
    "            for itemA, itemB in zip(valueA, valueB):\n",
    "                if orderDic[itemA] != orderDic[itemB]:\n",
    "                    return orderDic[itemA]<orderDic[itemB]\n",
    "            return len(valueA)<=len(valueB)\n",
    "        orderDic={value:key for key, value in enumerate(order)}\n",
    "        return all(checkOrder(valueA, valueB) for valueA, valueB in zip(words, words[1:]))\n",
    "\n",
    "        # MAP 逐个遍历\n",
    "        ind = {c: i for i, c in enumerate(order)}\n",
    "        for a, b in zip(words, words[1:]):  # 自配对 1&2 2&3 3&4 ...\n",
    "            if len(a) > len(b) and a[:len(b)] == b:  # case abcde&abc \n",
    "                return False\n",
    "            for s1, s2 in zip(a, b):\n",
    "                if ind[s1] < ind[s2]:\n",
    "                    break\n",
    "                elif ind[s1] > ind[s2]:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "        # MAP C->INT\n",
    "        dic = {}\n",
    "        for i, c in enumerate(order):\n",
    "            dic[c] = str(i + 10)\n",
    "        pre = '0'\n",
    "        for w in words:\n",
    "            cur = ''\n",
    "            for c in w:\n",
    "                cur += dic[c]\n",
    "            mx = max(len(cur), len(pre))\n",
    "            if int(pre + '0' * (mx-len(pre))) > int(cur + '0' * (mx-len(cur))): \n",
    "                return False\n",
    "            pre = cur\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        dic = {}\n",
    "        for i, c in enumerate(order):\n",
    "            dic[c] = str(i + 10)\n",
    "        #print(dic)\n",
    "        pre = '0'\n",
    "        for w in words:\n",
    "            cur = ''\n",
    "            for c in w:\n",
    "                cur += dic[c]\n",
    "            mx = max(len(cur), len(pre))\n",
    "            #print(pre, cur)\n",
    "            if int(pre + '0' * (mx-len(pre))) > int(cur + '0' * (mx-len(cur))): \n",
    "                return False\n",
    "            pre = cur\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        n = len(words)\n",
    "        for i in range(n-1):\n",
    "            n1 = len(words[i])\n",
    "            n2 = len(words[i+1])\n",
    "            k = n2 if n1>n2 else n1\n",
    "            for j in range(k):\n",
    "                if words[i][j] == words[i+1][j]:\n",
    "                    continue\n",
    "                else:\n",
    "                    inx1 = order.find(words[i][j])\n",
    "                    indx2 = order.find(words[i+1][j])\n",
    "                    if inx1 > indx2:\n",
    "                        return False\n",
    "                    break\n",
    "            else:        \n",
    "                if n1 > n2:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        n = len(words)\n",
    "        for i in range(n-1) :\n",
    "            cur = words[i] \n",
    "            nex = words[i+1]\n",
    "            pos = 0 \n",
    "            while pos < len(cur) and pos < len(nex) and cur[pos] == nex[pos] :\n",
    "                pos += 1 \n",
    "            if pos == len(cur) and pos < len(nex) :  # cur 更短，优先级更高\n",
    "                continue\n",
    "            elif pos == len(nex) and pos < len(cur) :\n",
    "                return False  # nex更短，优先级更高，但是排在了后面，所以返回False\n",
    "            # 如果都不是，那就是遇到了第一个不相同的字符了\n",
    "            if pos < len(cur) and pos < len(nex) and order.index(cur[pos]) > order.index(nex[pos]) :\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        checker = {}\n",
    "        for i, o in enumerate(order):\n",
    "            checker[o] = i+1\n",
    "\n",
    "        # check every word and calculate word order\n",
    "        for w1, w2 in pairwise(words):\n",
    "            check_pos = 0\n",
    "            while check_pos < len(w1):\n",
    "                if check_pos == len(w2) or checker[w1[check_pos]] - checker[w2[check_pos]] > 0:\n",
    "                    return False\n",
    "                elif checker[w1[check_pos]] - checker[w2[check_pos]] < 0:\n",
    "                    break\n",
    "                check_pos += 1\n",
    "                \n",
    "                # no length overtake or corresponding order overtake\n",
    "\n",
    "        return True\n",
    "                \n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        m = dict((c, i) for i, c in enumerate(order))\n",
    "        for i in range(len(words) - 1):\n",
    "            a, b = words[i], words[i + 1]\n",
    "            ai, bi, aa, bb = 0, 0, len(a), len(b)\n",
    "            while ai < aa or bi < bb:\n",
    "                c = -1 if ai >= aa else m[a[ai]]\n",
    "                d = -1 if bi >= bb else m[b[bi]]\n",
    "                if c < d: break\n",
    "                if c > d: return False\n",
    "                ai += 1\n",
    "                bi += 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        dic = {char: chr(idx + ord('a')) for idx, char in enumerate(order)}\n",
    "        lst = [''.join([dic[char] for char in word]) for word in words]\n",
    "        return sorted(lst) == lst\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        order_ = {}\n",
    "        for i, c in enumerate(order):\n",
    "            order_[c] = i \n",
    "        \n",
    "        def cmp_two_words(w1, w2):\n",
    "            p = 0\n",
    "            smaller = False\n",
    "            while p<len(w1) and p<len(w2) and w1[p] == w2[p]:\n",
    "                p+=1\n",
    "                continue\n",
    "\n",
    "            if p < len(w1) and p == len(w2):\n",
    "                return False\n",
    "            if p == len(w1) or order_[w1[p]] < order_[w2[p]]:\n",
    "                smaller = True\n",
    "            return smaller\n",
    "        \n",
    "\n",
    "        for i, w in enumerate(words[:-1]):\n",
    "            if not cmp_two_words(w, words[i+1]):\n",
    "                return False\n",
    "\n",
    "\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "      index = {c:i for i,c in enumerate(order)}\n",
    "      return all(s <= t for s , t in pairwise([index[c] for c in word] for word in words))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        # MAP 遍历\n",
    "        ind = {c: i for i, c in enumerate(order)}\n",
    "        for a, b in zip(words, words[1:]):\n",
    "            if len(a) > len(b) and a[:len(b)] == b:\n",
    "                return False\n",
    "            for s1, s2 in zip(a, b):\n",
    "                if ind[s1] < ind[s2]:\n",
    "                    break\n",
    "                elif ind[s1] > ind[s2]:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "        # MAP C->INT\n",
    "        dic = {}\n",
    "        for i, c in enumerate(order):\n",
    "            dic[c] = str(i + 10)\n",
    "        pre = '0'\n",
    "        for w in words:\n",
    "            cur = ''\n",
    "            for c in w:\n",
    "                cur += dic[c]\n",
    "            mx = max(len(cur), len(pre))\n",
    "            if int(pre + '0' * (mx-len(pre))) > int(cur + '0' * (mx-len(cur))): \n",
    "                return False\n",
    "            pre = cur\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        f = False\n",
    "        \n",
    "        for i in range(len(words) - 1):\n",
    "            for j in range(i + 1, len(words)):\n",
    "                s1, s2 = words[i], words[j]\n",
    "\n",
    "                if s1 == s2:\n",
    "                    f = True\n",
    "                    break\n",
    "\n",
    "                k = 0\n",
    "                while k < len(s1):\n",
    "                    if k < len(s2) and order.index(s1[k]) > order.index(s2[k]):\n",
    "                        return False\n",
    "                    elif k < len(s2) and order.index(s1[k]) < order.index(s2[k]):\n",
    "                        f = True\n",
    "                        break    \n",
    "                    k += 1\n",
    "\n",
    "                if k < len(s2):\n",
    "                    f = True\n",
    "                else:\n",
    "                    f = False\n",
    "    \n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        h = dict()\n",
    "        for i in range(len(order)):\n",
    "            h[order[i]] = i\n",
    "        for i in range(len(words) - 1):\n",
    "            a,b = words[i],words[i + 1]\n",
    "            n = min(len(a),len(b))\n",
    "            for j in range(n + 1):\n",
    "                if j == n:\n",
    "                    if len(a) > len(b):\n",
    "                        return False\n",
    "                elif h[a[j]] < h[b[j]]:\n",
    "                    break\n",
    "                elif h[a[j]] > h[b[j]]:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        ans = [0] * 26\n",
    "        for i in range(len(order)):\n",
    "            ans[i] = order[i]\n",
    "        for i in range(1, len(words)):\n",
    "            j = 0\n",
    "            while j < min(len(words[i]), len(words[i-1])):\n",
    "                if ans.index(words[i-1][j]) < ans.index(words[i][j]):\n",
    "                    break\n",
    "                elif ans.index(words[i-1][j]) > ans.index(words[i][j]):\n",
    "                    return False\n",
    "                else:\n",
    "                    j += 1\n",
    "            if j == len(words[i]) and j < len(words[i-1]):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:        \n",
    "        for i in range(len(words)-1):\n",
    "            pre = [order.index(x) for x in words[i]]\n",
    "            cur = [order.index(x) for x in words[i+1]]\n",
    "            #print(pre,cur)\n",
    "            if pre > cur:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        for i in range(len(words)-1):\n",
    "            if words[i]==words[i+1]:\n",
    "                continue\n",
    "            for j in range(0,min(len(words[i]),len(words[i+1]))):\n",
    "                if order.index(words[i][j])<order.index(words[i+1][j]):\n",
    "                    j-=1\n",
    "                    break\n",
    "                elif order.index(words[i][j])>order.index(words[i+1][j]):\n",
    "                    return False\n",
    "            if j==len(words[i+1])-1 :\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        index = {c: i for i, c in enumerate(order)}\n",
    "        return all(s <= t for s, t in pairwise([index[c] for c in word] for word in words))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: list[str], order: str) -> bool:\n",
    "        od = {v:i for i, v in enumerate(order)}\n",
    "        pre = [od[w] for w in words[0]]\n",
    "        for i in range(1, len(words)):\n",
    "            cur = [od[w] for w in words[i]]\n",
    "            if cur < pre:\n",
    "                return False\n",
    "            pre = cur\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        alien_dict = {}\n",
    "        for i, c in enumerate(order):\n",
    "            alien_dict[c] = i\n",
    "        \n",
    "        for i in range(1, len(words)):\n",
    "            j = 0\n",
    "            while j < len(words[i]) and j < len(words[i - 1]):\n",
    "                if alien_dict[words[i][j]] > alien_dict[words[i - 1][j]]:\n",
    "                    break\n",
    "                elif alien_dict[words[i][j]] == alien_dict[words[i - 1][j]]:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    return False\n",
    "            if len(words[i]) < len(words[i - 1]) and words[i - 1].startswith(words[i]):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        order_dict = dict()\n",
    "        for id, char in enumerate(order):\n",
    "            order_dict[char] = id\n",
    "\n",
    "        def judge(word1: str, word2: str) -> bool:\n",
    "            length = min(len(word1), len(word2))\n",
    "            char_pointer = 0\n",
    "            while char_pointer < length:\n",
    "                od1 = order_dict[word1[char_pointer]]\n",
    "                od2 = order_dict[word2[char_pointer]]\n",
    "                if od1 > od2 :\n",
    "                    return False\n",
    "                elif od1 < od2 :\n",
    "                    return True\n",
    "                else:\n",
    "                    char_pointer += 1\n",
    "            return len(word1) <= len(word2)\n",
    "        \n",
    "        for index in range(0, len(words) - 1):\n",
    "            if not judge(words[index], words[index + 1]):\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        def compare(w1,w2,d):\n",
    "            for i in range(len(w1)):\n",
    "                if i>=len(w2):\n",
    "                    return False\n",
    "                if d[w1[i]]<d[w2[i]]:\n",
    "                    return True\n",
    "                if d[w1[i]]>d[w2[i]]:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        d={order[i]:i for i in range(len(order))}\n",
    "        for i in range(len(words)-1):\n",
    "            if not compare(words[i],words[i+1],d):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        f = False\n",
    "        index = {c: i for i, c in enumerate(order)}\n",
    "        for i in range(len(words) - 1):\n",
    "            for j in range(i + 1, len(words)):\n",
    "                s1, s2 = words[i], words[j]\n",
    "\n",
    "                if s1 == s2:\n",
    "                    f = True\n",
    "                    break\n",
    "\n",
    "                k = 0\n",
    "                while k < len(s1):\n",
    "                    if k < len(s2) and index[s1[k]] > index[s2[k]]:\n",
    "                        return False\n",
    "                    elif k < len(s2) and index[s1[k]] < index[s2[k]]:\n",
    "                        f = True\n",
    "                        break    \n",
    "                    k += 1\n",
    "\n",
    "                if k < len(s2):\n",
    "                    f = True\n",
    "                else:\n",
    "                    f = False\n",
    "    \n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        mp = {c:i for i, c in enumerate(order)}\n",
    "        #return all(s <= t for s, t in pairwise([index[c] for c in word] for word in words))\n",
    "        n = len(words)\n",
    "        for i in range(1, n):\n",
    "\n",
    "            str1 = words[i-1]\n",
    "            str2 = words[i]\n",
    "\n",
    "            j = 0\n",
    "            valid = False\n",
    "            while j < len(str1) and j < len(str2):\n",
    "                if mp[str1[j]] > mp[str2[j]]:\n",
    "                    return False # 字典序反了，直接返回失败\n",
    "                elif mp[str1[j]] < mp[str2[j]]:\n",
    "                    valid = True\n",
    "                    break # 字典序符合，退出并比较下一组word\n",
    "                j += 1 # 字典序相同，还要比下一个字符\n",
    "\n",
    "            if not valid:\n",
    "                # 比较完了，有个字符较长，长的字典序要大，短的应该排在前面\n",
    "                if len(str1) > len(str2):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        mp = {c: i for i, c in enumerate(order)}\n",
    "        for i, w in enumerate(words[:-1]):\n",
    "            j = 0\n",
    "            while j < len(w):\n",
    "                if j == len(words[i + 1]) or (a := mp[w[j]] - mp[words[i + 1][j]]) > 0:\n",
    "                    return False\n",
    "                elif a < 0:\n",
    "                    break\n",
    "                j += 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        d = str.maketrans(order, ascii_lowercase)\n",
    "        print(d)\n",
    "        for w1, w2 in pairwise(words):\n",
    "            if w1.translate(d)>w2.translate(d):\n",
    "                return False\n",
    "        return True\n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        list1 = list(order)\n",
    "        length = len(words[0])\n",
    "        for i in range(len(words)):\n",
    "            if len(words[i]) < length:\n",
    "                length = len(words[i])\n",
    "        a = 0\n",
    "        while a<length:\n",
    "            x = 0\n",
    "            for i in range(len(words)):\n",
    "                \n",
    "                if i+1>=len(words):\n",
    "                    pass\n",
    "                elif list1.index(words[i][a]) < list1.index(words[i+1][a]):\n",
    "                    x = x+1\n",
    "                elif list1.index(words[i][a]) > list1.index(words[i+1][a]):\n",
    "                    return False\n",
    "                else:\n",
    "                    pass\n",
    "                if x == len(words)-1:\n",
    "                    return True\n",
    "            a = a+1\n",
    "        y = 0\n",
    "        for i in range(len(words)):\n",
    "            \n",
    "            if i+1>=len(words):\n",
    "                pass\n",
    "            elif len(words[i]) > len(words[i+1]):\n",
    "                return False\n",
    "            elif len(words[i]) < len(words[i+1]):\n",
    "                y = y+1\n",
    "                if y == len(words)-1:\n",
    "                    return True\n",
    "        for i in range(len(words)):\n",
    "            if i+1>=len(words):\n",
    "                pass\n",
    "            elif len(words[i]) == len(words[i+1]):\n",
    "                a = words[i]\n",
    "                b = words[i+1]\n",
    "                try:\n",
    "                    while True:\n",
    "                        if list1.index(a[length]) > list1.index(b[length]):\n",
    "                            return False\n",
    "                        else:\n",
    "                            \n",
    "                            length = length+1\n",
    "                except:\n",
    "                    pass\n",
    "        if not any(words[i] != words[i+1] for i in range(len(words)-1)):\n",
    "            return True  \n",
    "        return True      \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        index = {c: i for i, c in enumerate(order)}\n",
    "        return all(s <= t for s, t in pairwise([index[c] for c in word] for word in words))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        index = {c: i for i, c in enumerate(order)}\n",
    "        return all(s <= t for s, t in pairwise([index[c] for c in word] for word in words))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        seq = {}\n",
    "        for i in range(len(order)):\n",
    "            seq[order[i]] = i\n",
    "\n",
    "        words = [[seq[c] for c in w] for w in words]\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i + 1, len(words), 1):\n",
    "                w1 = words[i]\n",
    "                w2 = words[j]\n",
    "                if w1 > w2:\n",
    "                    return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        order_dict = dict()\n",
    "        for id, char in enumerate(order):\n",
    "            order_dict[char] = id\n",
    "\n",
    "        def judge(word1: str, word2: str) -> bool:\n",
    "            length = min(len(word1), len(word2))\n",
    "            char_pointer = 0\n",
    "            while char_pointer < length:\n",
    "                od1 = order_dict[word1[char_pointer]]\n",
    "                od2 = order_dict[word2[char_pointer]]\n",
    "                if od1 > od2 :\n",
    "                    return False\n",
    "                elif od1 < od2 :\n",
    "                    return True\n",
    "                else:\n",
    "                    char_pointer += 1\n",
    "            return len(word1) <= len(word2)\n",
    "        \n",
    "        for index in range(0, len(words) - 1):\n",
    "            if not judge(words[index], words[index + 1]):\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        mapping = dict()\n",
    "        for i,ch in enumerate(order):\n",
    "            mapping[ch] = chr(i + ord('a'))\n",
    "        \n",
    "        res_list = []\n",
    "        for i, word in enumerate(words):\n",
    "            string = ''\n",
    "            for ch in word:\n",
    "                string += mapping[ch]\n",
    "            res_list.append(string)\n",
    "        \n",
    "        for i in range(len(res_list) - 1):\n",
    "            if res_list[i] > res_list[i + 1]:\n",
    "                return False\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        store = defaultdict(int)\n",
    "        start = 0\n",
    "        for i in order:\n",
    "            store[i] = start\n",
    "            start += 1\n",
    "        for i in range(1,len(words)):\n",
    "            j = 0\n",
    "            while j < len(words[i]) and j < len(words[i-1]):\n",
    "                if store[words[i-1][j]] < store[words[i][j]]:\n",
    "                    break\n",
    "                elif words[i-1][j] == words[i][j]:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    return False\n",
    "            if j == len(words[i]) and j < len(words[i-1]):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        for i in range(len(words) - 1):\n",
    "            tail_flag = True\n",
    "            for j in range(min(len(words[i]), len(words[i + 1]))):\n",
    "                print(i, j)\n",
    "                if order.index(words[i][j]) > order.index(words[i + 1][j]):\n",
    "                    # print(order.index(words[i][j]), order.index(words[i + 1][j]))\n",
    "                    # print(words[i], words[i + 1])\n",
    "                    return False\n",
    "                if order.index(words[i][j]) < order.index(words[i + 1][j]):\n",
    "                    tail_flag = False\n",
    "                    break\n",
    "            # 如果还没分出，继续判断剩余的字符\n",
    "            if tail_flag:\n",
    "                if len(words[i]) > len(words[i + 1]):\n",
    "                    print('a')\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        def valid(str1, str2):\n",
    "            str1_len, str2_len = len(str1), len(str2)\n",
    "            for i in range(min(str1_len, str2_len)):\n",
    "                if char_rank[str1[i]] < char_rank[str2[i]]: return True\n",
    "                if char_rank[str1[i]] > char_rank[str2[i]]: return False\n",
    "            return str1_len <= str2_len\n",
    "\n",
    "        char_rank, n = {char: i for i, char in enumerate(order)}, len(words)\n",
    "        for i in range(n - 1):\n",
    "            if not valid(words[i], words[i + 1]): return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        dic = {ch: i for i, ch in enumerate(order)}\n",
    "        for w1, w2 in zip(words, words[1:]):\n",
    "            # already know len(w2) < len(w1)\n",
    "            # if len(w1) > len(w2) and w1[: len(w2)] == w2:\n",
    "            if len(w1) > len(w2) and w1[: min(len(w1), len(w2))] == w2[: min(len(w1), len(w2))] :\n",
    "                return False\n",
    "            for c1, c2 in zip(w1, w2):\n",
    "                if c1 == c2:\n",
    "                    continue\n",
    "                if dic[c1] > dic[c2]:\n",
    "                    return False\n",
    "                break\n",
    "        return True \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        index = {c: i for i, c in enumerate(order)}\n",
    "        prev = []\n",
    "        for word in words:\n",
    "            mapped_word = [index[c] for c in word]\n",
    "            found = False\n",
    "            if prev:\n",
    "                word1, word2 = [v for v in prev], [v for v in mapped_word]\n",
    "                while word1 and word2:\n",
    "                    w1, w2 = word1.pop(0), word2.pop(0)\n",
    "                    if w1 > w2:\n",
    "                        return False\n",
    "                    elif w1 < w2:\n",
    "                        found = True\n",
    "                        break\n",
    "                if len(word1) != 0 and len(word2) == 0 and not found:\n",
    "                    return False\n",
    "            prev = mapped_word\n",
    "        return True\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        f = False\n",
    "        \n",
    "        for i in range(len(words) - 1):\n",
    "            for j in range(i + 1, len(words)):\n",
    "                s1, s2 = words[i], words[j]\n",
    "\n",
    "                if s1 == s2:\n",
    "                    f = True\n",
    "                    break\n",
    "\n",
    "                k = 0\n",
    "                while k < len(s1):\n",
    "                    if k < len(s2) and order.index(s1[k]) > order.index(s2[k]):\n",
    "                        return False\n",
    "                    elif k < len(s2) and order.index(s1[k]) < order.index(s2[k]):\n",
    "                        f = True\n",
    "                        break    \n",
    "                    k += 1\n",
    "\n",
    "                if k < len(s2):\n",
    "                    f = True\n",
    "                else:\n",
    "                    f = False\n",
    "    \n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        dict_order={}\n",
    "        for i,c in enumerate(order):\n",
    "            if c not in dict_order:\n",
    "                dict_order[c]=i\n",
    "        for i in range(len(words)-1):\n",
    "            for j in range(min(len(words[i]),len(words[i+1]))):\n",
    "                if words[i][j]!=words[i+1][j]:\n",
    "                    if dict_order[words[i][j]]<dict_order[words[i+1][j]]:\n",
    "                        break\n",
    "                    else:\n",
    "                        return False\n",
    "            else:\n",
    "                if len(words[i])>len(words[i+1]):\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "                    \n",
    "                 \n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        idx = {}\n",
    "        for i, c in enumerate(order):\n",
    "            idx[c] = i\n",
    "        for i in range(len(words)):\n",
    "            for j in range(i + 1, len(words)):\n",
    "                small, big = words[i], words[j]\n",
    "                if len(small) > len(big) and small[:len(big)] == big:\n",
    "                    return False\n",
    "                for k in range(len(small)):\n",
    "                    if idx[small[k]] > idx[big[k]]:\n",
    "                        return False\n",
    "                    elif idx[small[k]] == idx[big[k]]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        break\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        index = {c: i for i, c in enumerate(order)}\n",
    "        return all (s<=t for s, t in pairwise([index[c] for c in word] for word in words))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        d = dict()\n",
    "        for i, c in enumerate(order):\n",
    "            d[c] = i\n",
    "\n",
    "        pre = [d[c] for c in words[0]]\n",
    "        for w in words[1:]:\n",
    "            new_w = [d[c] for c in w]\n",
    "            if pre > new_w:\n",
    "                return False\n",
    "            pre = new_w\n",
    "            \n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isAlienSorted(self, words: List[str], order: str) -> bool:\n",
    "        checker = {}\n",
    "        for i, o in enumerate(order):\n",
    "            checker[o] = i+1\n",
    "\n",
    "        # check every word and calculate word order\n",
    "        for w1, w2 in pairwise(words):\n",
    "            check_pos = 0\n",
    "            while check_pos < len(w1):\n",
    "                if check_pos == len(w2):\n",
    "                    return False\n",
    "                \n",
    "                if checker[w1[check_pos]] - checker[w2[check_pos]] > 0:\n",
    "                    return False\n",
    "                if checker[w1[check_pos]] - checker[w2[check_pos]] < 0:\n",
    "                    break\n",
    "                check_pos += 1\n",
    "                \n",
    "                # no length overtake or corresponding order overtake\n",
    "\n",
    "        return True\n",
    "                \n",
    "                \n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
